package de.unikoblenz.west.csxpoi.server;

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.GregorianCalendar;
import java.util.List;
import java.util.TimeZone;

import org.openrdf.query.BindingSet;
import org.openrdf.query.MalformedQueryException;
import org.openrdf.query.QueryEvaluationException;
import org.openrdf.query.QueryLanguage;
import org.openrdf.query.TupleQuery;
import org.openrdf.query.TupleQueryResult;
import org.openrdf.repository.Repository;
import org.openrdf.repository.RepositoryConnection;
import org.openrdf.repository.RepositoryException;
import org.openrdf.repository.http.HTTPRepository;

import uk.ac.shef.wit.simmetrics.similaritymetrics.AbstractStringMetric;
import uk.ac.shef.wit.simmetrics.similaritymetrics.JaroWinkler;

/**
 * Methods for calculating the similarity of POIs.
 */
public abstract class Similarity {

	/**
	 * Calculates the (asymmetric) similarity of two specified POIs linearly
	 * combining linguistic, spatial, and semantic simiarities.
	 * 
	 * @param target
	 *            the target POI
	 * @param base
	 *            the base POI
	 * @return a similarity value between 0 (minimum) and 1 (maximum)
	 * @throws SimilarityException
	 */

	public abstract double similarity(PoiWrapper target, PoiWrapper base)
			throws SimilarityException;

	/**
	 * Calculates the (symmetric) linguistic similarity of two specified POIs by
	 * comparing their names.
	 * 
	 * @param first
	 *            the first POI
	 * @param second
	 *            the second POI
	 * @return a similarity value between 0 (minimum) and 1 (maximum)
	 * @throws SimilarityException
	 */
	public double linguisticSimilarity(PoiWrapper first, PoiWrapper second) {

		// TODO: determine optimal metric

		return jaroWinkler(first.getName(), second.getName());

	}

	/**
	 * Calculates the (symmetric) spatial similarity of two specified POIs by
	 * comparing their locations.
	 * 
	 * @param first
	 *            the first POI
	 * @param second
	 *            the second POI
	 * @return a similarity value between 0 (minimum) and 1 (maximum)
	 * @throws SimilarityException
	 */
	public double spatialSimilarity(PoiWrapper first, PoiWrapper second) {

		double distance = vincenty(first.getLatitude(), first.getLongitude(),
				second.getLatitude(), second.getLongitude());

		double hd = 200; // distance in meters for which similarity is 0.5
		double a = -Math.log(0.5) / hd;

		double similarity = Math.exp(-a * distance);

		return similarity;
	}

	/**
	 * Calculates the (asymmetric) semantic similarity of two specified POIs by
	 * implementing the MDSM similarity metric.
	 * 
	 * @param target
	 *            the target POI
	 * @param base
	 *            the base POI
	 * @return a similarity value between 0 (minimum) and 1 (maximum)
	 * @throws SimilarityException
	 */
	public double semanticSimilarity(PoiWrapper target, PoiWrapper base)
			throws SimilarityException {

		double similarity = 0;

		Repository repository = new HTTPRepository(Constants.SESAME_SERVER,
				Constants.REPOSITORY_ID);

		try {
			repository.initialize();
			RepositoryConnection connection = repository.getConnection();

			try {
				int intersectingCategories = 0;
				int targetOnlyCategories = 0;
				for (CategoryWrapper category : target.getCategories()) {
					if (base.getCategories().contains(category)) {
						intersectingCategories++;
					} else {
						targetOnlyCategories++;
					}
				}
				int baseOnlyCategories = 0;
				for (CategoryWrapper category : base.getCategories()) {
					if (!target.getCategories().contains(category)) {
						baseOnlyCategories++;
					}
				}

				CategoryWrapper leastUpperBound = leastUpperBound(target, base,
						connection);
				int targetDistance = hierarchicalDistance(target,
						leastUpperBound, connection);
				int baseDistance = hierarchicalDistance(base, leastUpperBound,
						connection);

				if (targetDistance + baseDistance == 0)
					similarity = 1; // identical

				double relativeDistance = (double) targetDistance
						/ (targetDistance + baseDistance);

				double alpha;
				if (targetDistance <= baseDistance) {
					alpha = relativeDistance;
				} else {
					alpha = 1 - relativeDistance;
				}

				similarity = (double) intersectingCategories
						/ (intersectingCategories + alpha
								* targetOnlyCategories + (1 - alpha)
								* baseOnlyCategories);

			} catch (MalformedQueryException e) {
				throw new SimilarityException();
			} catch (QueryEvaluationException e) {
				throw new SimilarityException();
			} finally {
				connection.close();
			}
		} catch (RepositoryException e) {
			throw new SimilarityException();
		}

		return similarity;
	}

	/**
	 * Calculates the timely similarity of two specified Events by comparing
	 * their time span.
	 * 
	 * @param first
	 *            the first Event
	 * @param second
	 *            the second Event
	 * @return a similarity value between 0 (minimum) and 1 (maximum)
	 * @throws SimilarityException
	 */
	public double temporarySimilarity(PoiWrapper first, PoiWrapper second)
			throws SimilarityException {

		// Time interval not well defined
		if (first.getStartDate() == "" || second.getStartDate() == ""
				|| first.getEndDate() == "" || second.getEndDate() == "")
			throw new SimilarityException();

		long startDateFirst = 0, startDateSecond = 0, endDateFirst = 0, endDateSecond = 0, temp = 0, overallTimespan = 0, overlapTimespan = 0;

		// Transform to dates to long
		startDateFirst = dateToMillis(first.getStartDate());
		startDateSecond = dateToMillis(second.getStartDate());
		endDateFirst = dateToMillis(first.getEndDate());
		endDateSecond = dateToMillis(second.getEndDate());

		if (startDateFirst > startDateSecond) {
			temp = startDateFirst;
			startDateFirst = startDateSecond;
			startDateSecond = temp;
			temp = endDateFirst;
			endDateFirst = endDateSecond;
			endDateSecond = temp;
		}
		;

		// time intervals disjunct
		if (startDateSecond > endDateFirst){
			return 0;
//			throw new SimilarityException();
		}

		overallTimespan = endDateSecond - startDateFirst;
		if (overallTimespan == 0)
			return 0;

		overlapTimespan = overallTimespan - (startDateSecond - startDateFirst)
				- (endDateSecond - endDateFirst);

		return overlapTimespan / overallTimespan;

	}

	
	
	private long dateToMillis(String poiTimeStamp) {
		if (poiTimeStamp != null && poiTimeStamp != "" && poiTimeStamp != " ") {
			try {

				poiTimeStamp = poiTimeStamp.replace("'", "");
				poiTimeStamp = poiTimeStamp.replace(" ", "");

				Calendar calendar = new GregorianCalendar();
				Date newDate = null;
				try {
					DateFormat format = new SimpleDateFormat(
							"yyyy-mm-dd'T'hh:mm:ss'Z'");
					newDate = (Date) format.parse(poiTimeStamp);
					calendar.setTime(newDate);
				} catch (Exception e) {
					DateFormat format = new SimpleDateFormat(
							"yyyy-m-d'T'hh:mm:ss'Z'");
					newDate = (Date) format.parse(poiTimeStamp);
					calendar.setTime(newDate);
				}

				return calendar.getTimeInMillis();

			} catch (Exception e) {
//				e.printStackTrace();
			}
		}

		return 0;

	}
	

	/**
	 * Calculates the Jaro-Winkler similarity of two specified strings.
	 * 
	 * @param first
	 *            the first string
	 * @param second
	 *            the second string
	 * @return a similarity value between 0 (minimum) and 1 (maximum)
	 */
	private double jaroWinkler(String first, String second) {

		AbstractStringMetric metric = new JaroWinkler();

		return metric.getSimilarity(first, second);
	}

	/**
	 * Calculates the metric distance between two specified geographic points
	 * using Vincenty's formulae.
	 * 
	 * @param lat1
	 *            the latitude of the first point
	 * @param lon1
	 *            the longitude of the first point
	 * @param lat2
	 *            the latitude of the second point
	 * @param lon2
	 *            the longitude of the second point
	 * @return
	 */
	private double vincenty(double lat1, double lon1, double lat2, double lon2) {

		// From http://bit.ly/vincenty

		// Based on http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf
		// using the "Inverse Formula" (section 4)

		int MAXITERS = 20;
		// Convert lat/long to radians
		lat1 *= Math.PI / 180.0;
		lat2 *= Math.PI / 180.0;
		lon1 *= Math.PI / 180.0;
		lon2 *= Math.PI / 180.0;

		double a = 6378137.0; // WGS84 major axis
		double b = 6356752.3142; // WGS84 semi-major axis
		double f = (a - b) / a;
		double aSqMinusBSqOverBSq = (a * a - b * b) / (b * b);

		double L = lon2 - lon1;
		double A = 0.0;
		double U1 = Math.atan((1.0 - f) * Math.tan(lat1));
		double U2 = Math.atan((1.0 - f) * Math.tan(lat2));

		double cosU1 = Math.cos(U1);
		double cosU2 = Math.cos(U2);
		double sinU1 = Math.sin(U1);
		double sinU2 = Math.sin(U2);
		double cosU1cosU2 = cosU1 * cosU2;
		double sinU1sinU2 = sinU1 * sinU2;

		double sigma = 0.0;
		double deltaSigma = 0.0;
		double cosSqAlpha = 0.0;
		double cos2SM = 0.0;
		double cosSigma = 0.0;
		double sinSigma = 0.0;
		double cosLambda = 0.0;
		double sinLambda = 0.0;

		double lambda = L; // initial guess
		for (int iter = 0; iter < MAXITERS; iter++) {
			double lambdaOrig = lambda;
			cosLambda = Math.cos(lambda);
			sinLambda = Math.sin(lambda);
			double t1 = cosU2 * sinLambda;
			double t2 = cosU1 * sinU2 - sinU1 * cosU2 * cosLambda;
			double sinSqSigma = t1 * t1 + t2 * t2; // (14)
			sinSigma = Math.sqrt(sinSqSigma);
			cosSigma = sinU1sinU2 + cosU1cosU2 * cosLambda; // (15)
			sigma = Math.atan2(sinSigma, cosSigma); // (16)
			double sinAlpha = (sinSigma == 0) ? 0.0 : cosU1cosU2 * sinLambda
					/ sinSigma; // (17)
			cosSqAlpha = 1.0 - sinAlpha * sinAlpha;
			cos2SM = (cosSqAlpha == 0) ? 0.0 : cosSigma - 2.0 * sinU1sinU2
					/ cosSqAlpha; // (18)

			double uSquared = cosSqAlpha * aSqMinusBSqOverBSq; // defn
			A = 1
					+ (uSquared / 16384.0)
					* // (3)
					(4096.0 + uSquared
							* (-768 + uSquared * (320.0 - 175.0 * uSquared)));
			double B = (uSquared / 1024.0) * // (4)
					(256.0 + uSquared
							* (-128.0 + uSquared * (74.0 - 47.0 * uSquared)));
			double C = (f / 16.0) * cosSqAlpha
					* (4.0 + f * (4.0 - 3.0 * cosSqAlpha)); // (10)
			double cos2SMSq = cos2SM * cos2SM;
			deltaSigma = B
					* sinSigma
					* // (6)
					(cos2SM + (B / 4.0)
							* (cosSigma * (-1.0 + 2.0 * cos2SMSq) - (B / 6.0)
									* cos2SM
									* (-3.0 + 4.0 * sinSigma * sinSigma)
									* (-3.0 + 4.0 * cos2SMSq)));

			lambda = L
					+ (1.0 - C)
					* f
					* sinAlpha
					* (sigma + C
							* sinSigma
							* (cos2SM + C * cosSigma
									* (-1.0 + 2.0 * cos2SM * cos2SM))); // (11)

			double delta = (lambda - lambdaOrig) / lambda;
			if (Math.abs(delta) < 1.0e-12) {
				break;
			}
		}

		return b * A * (sigma - deltaSigma);
	}

	/**
	 * Determines the least upper bound of two specified POIs within the
	 * hierarchy of their categories.
	 * 
	 * @param first
	 *            the first POI
	 * @param second
	 *            the second POI
	 * @param connection
	 *            a repository connection
	 * @return the least upperbound of the two POIs
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 */
	private CategoryWrapper leastUpperBound(PoiWrapper first,
			PoiWrapper second, RepositoryConnection connection)
			throws RepositoryException, MalformedQueryException,
			QueryEvaluationException {

		CategoryWrapper category = null;

		// TODO: ontology may not be partially ordered -> multiple least upper
		// bounds

		TupleQuery query = connection.prepareTupleQuery(
				QueryLanguage.SPARQL,
				"PREFIX rdfs: <" + Constants.NS_RDFS + "> "
						+ "SELECT ?lub WHERE {" + " ?poi1 a ?lub ."
						+ " ?poi2 a ?lub ." + " OPTIONAL {" + "  ?poi1 a ?ub ."
						+ "  ?poi2 a ?ub ." + "  ?ub rdfs:subClassOf ?lub ."
						+ "  FILTER (?ub != ?lub)" + " }"
						+ " FILTER (!bound(?ub))" + " FILTER (?poi1 = <"
						+ first.getUri() + ">" + "  && ?poi2 = <"
						+ second.getUri() + ">)" + "}");
		TupleQueryResult result = query.evaluate();
		try {
			if (result.hasNext()) {
				BindingSet bindingSet = result.next();
				category = new CategoryWrapper(bindingSet.getBinding("lub")
						.getValue().stringValue(), null);
			}
		} finally {
			result.close();
		}

		return category;
	}

	/**
	 * Determines the least upper bound of two specified categories within their
	 * hierarchy.
	 * 
	 * @param first
	 *            the first category
	 * @param second
	 *            the second category
	 * @param connection
	 *            a repository connection
	 * @return the least upper bound of the two categories
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 */
	private CategoryWrapper leastUpperBound(CategoryWrapper first,
			CategoryWrapper second, RepositoryConnection connection)
			throws RepositoryException, MalformedQueryException,
			QueryEvaluationException {

		CategoryWrapper category = null;

		// TODO: ontology may not be partially ordered -> multiple least upper
		// bounds

		TupleQuery query = connection.prepareTupleQuery(
				QueryLanguage.SPARQL,
				"PREFIX rdfs: <" + Constants.NS_RDFS + "> "
						+ "SELECT ?lub WHERE {"
						+ " ?category1 rdfs:subClassOf ?lub ."
						+ " ?category2 rdfs:subClassOf ?lub ." + " OPTIONAL {"
						+ "  ?category1 rdfs:subClassOf ?ub ."
						+ "  ?category2 rdfs:subClassOf ?ub ."
						+ "  ?ub rdfs:subClassOf ?lub ."
						+ "  FILTER (?ub != ?lub)" + " }"
						+ " FILTER (!bound(?ub))" + " FILTER (?category1 = <"
						+ first.getUri() + ">" + "  && ?category2 = <"
						+ second.getUri() + ">)" + "} LIMIT 1");
		TupleQueryResult result = query.evaluate();
		try {
			if (result.hasNext()) {
				BindingSet bindingSet = result.next();
				category = new CategoryWrapper(bindingSet.getBinding("lub")
						.getValue().stringValue(), null);
			}
		} finally {
			result.close();
		}

		return category;
	}

	/**
	 * Counts the hierarchical distance from a specified POI to a specified
	 * category.
	 * 
	 * @param poi
	 *            the POI from which to start
	 * @param category
	 *            the category to which to get
	 * @param connection
	 *            a repository connection
	 * @return the hierarchical distance from the POI to the category
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 * @throws SimilarityException
	 */
	private int hierarchicalDistance(PoiWrapper poi, CategoryWrapper category,
			RepositoryConnection connection) throws RepositoryException,
			MalformedQueryException, QueryEvaluationException,
			SimilarityException {

		List<List<CategoryWrapper>> frontier = new ArrayList<List<CategoryWrapper>>();
		for (CategoryWrapper parent : directParents(poi, connection)) {
			List<CategoryWrapper> path = new ArrayList<CategoryWrapper>();
			path.add(parent);
			frontier.add(path);
		}

		return graphSearch(frontier, category, connection);
	}

	/**
	 * Counts the hierarchical distance from one specified category to another.
	 * 
	 * @param lower
	 *            the lower category
	 * @param upper
	 *            the upper category
	 * @param connection
	 *            a repository connection
	 * @return the hierarchical distance of the lower category to the upper one
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 * @throws SimilarityException
	 */
	private int hierarchicalDistance(CategoryWrapper lower,
			CategoryWrapper upper, RepositoryConnection connection)
			throws RepositoryException, MalformedQueryException,
			QueryEvaluationException, SimilarityException {

		List<List<CategoryWrapper>> frontier = new ArrayList<List<CategoryWrapper>>();
		List<CategoryWrapper> path = new ArrayList<CategoryWrapper>();
		path.add(lower);
		frontier.add(path);

		return graphSearch(frontier, upper, connection) - 1;
	}

	/**
	 * Performs a shortest-first graph search starting with an initial frontier
	 * (collection of paths) and counting the steps to the goal.
	 * 
	 * @param frontier
	 *            the initial frontier
	 * @param goal
	 *            the goal to reach
	 * @param connection
	 *            a repository connection
	 * @return the number of steps it took to reach the goal
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 * @throws SimilarityException
	 */
	private int graphSearch(List<List<CategoryWrapper>> frontier,
			CategoryWrapper goal, RepositoryConnection connection)
			throws RepositoryException, MalformedQueryException,
			QueryEvaluationException, SimilarityException {

		while (!frontier.isEmpty()) {

			List<CategoryWrapper> path = removeShortestPath(frontier);

			CategoryWrapper head = path.get(path.size() - 1);

			if (head.equals(goal))
				return path.size();

			List<CategoryWrapper> parents = directParents(head, connection);
			for (CategoryWrapper parent : parents) {
				List<CategoryWrapper> newPath = new ArrayList<CategoryWrapper>();
				newPath.addAll(path);
				newPath.add(parent);
				frontier.add(newPath);
			}
		}

		throw new SimilarityException(); // goal not found
	}

	/**
	 * Removes the shortest path from the specified froniter (collection of
	 * paths).
	 * 
	 * @param frontier
	 *            the frontier from which to remove the shortest path
	 * @return the shortest path from the frontier
	 */
	private List<CategoryWrapper> removeShortestPath(
			List<List<CategoryWrapper>> frontier) {

		if (frontier.isEmpty())
			return null;

		int shortestIndex = 0;
		int minimumSize = frontier.get(0).size();

		for (int i = 0; i < frontier.size(); i++) {
			List<CategoryWrapper> path = frontier.get(i);
			if (path.size() < minimumSize) {
				minimumSize = path.size();
				shortestIndex = i;
			}
		}

		return frontier.remove(shortestIndex);
	}

	/**
	 * Determines the direct parents (superclasses) of the specified category.
	 * 
	 * @param category
	 *            the category for which to determine the direct parents
	 * @param connection
	 *            a repository connection
	 * @return a list of direct parents of the specified category
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 */
	private List<CategoryWrapper> directParents(CategoryWrapper category,
			RepositoryConnection connection) throws RepositoryException,
			MalformedQueryException, QueryEvaluationException {

		List<CategoryWrapper> directParents = new ArrayList<CategoryWrapper>();

		TupleQuery query = connection.prepareTupleQuery(QueryLanguage.SPARQL,
				"PREFIX rdfs: <" + Constants.NS_RDFS + "> "
						+ "SELECT ?dp WHERE {"
						+ " ?class rdfs:subClassOf ?dp ."
						+ " FILTER (?dp != ?class)" + " OPTIONAL {"
						+ "  ?class rdfs:subClassOf ?p ."
						+ "  ?p rdfs:subClassOf ?dp ."
						+ "  FILTER (?p != ?dp && ?p != ?class)" + " }"
						+ " FILTER (!bound(?p))" + " FILTER (?class = <"
						+ category.getUri() + ">)" + "}");
		TupleQueryResult result = query.evaluate();
		try {
			while (result.hasNext()) {
				BindingSet bindingSet = result.next();
				directParents.add(new CategoryWrapper(bindingSet
						.getBinding("dp").getValue().stringValue(), null));
			}
		} finally {
			result.close();
		}

		return directParents;
	}

	/**
	 * Determines the direct parents (categories) of the specified POI.
	 * 
	 * @param poi
	 *            the POI for which to determine the direct parents
	 * @param connection
	 *            a repository connection
	 * @return a list of direct parents of the specified POI
	 * @throws RepositoryException
	 * @throws MalformedQueryException
	 * @throws QueryEvaluationException
	 */
	private List<CategoryWrapper> directParents(PoiWrapper poi,
			RepositoryConnection connection) throws RepositoryException,
			MalformedQueryException, QueryEvaluationException {

		List<CategoryWrapper> directParents = new ArrayList<CategoryWrapper>();

		TupleQuery query = connection.prepareTupleQuery(QueryLanguage.SPARQL,
				"PREFIX rdfs: <" + Constants.NS_RDFS + "> "
						+ "SELECT ?dp WHERE {" + " ?inst a ?dp ."
						+ " OPTIONAL {" + "  ?inst a ?p ."
						+ "  ?p rdfs:subClassOf ?dp ." + "  FILTER (?p != ?dp)"
						+ " }" + " FILTER (!bound(?p))" + " FILTER (?inst = <"
						+ poi.getUri() + ">)" + "}");
		TupleQueryResult result = query.evaluate();
		try {
			while (result.hasNext()) {
				BindingSet bindingSet = result.next();
				directParents.add(new CategoryWrapper(bindingSet
						.getBinding("dp").getValue().stringValue(), null));
			}
		} finally {
			result.close();
		}

		return directParents;
	}

}
